package com.hanxiaozhang.no10leetcode.backtrack;

import java.util.*;

/**
 * 〈一句话功能简述〉<br>
 * 〈电话号码的字母组合〉
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。
 * 2：{"a","b","c"}
 * 3:{"d","e","f"}
 * 4:{"g","h","i"}
 * 5:{"j","k","l"}
 * 6:{"m","n","o"}
 * 7:{"p","q","r","s"}
 * 8:{"t","u","v"}
 * 9:{"w","x","y","z"}
 * <p>
 * 示例 1：
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 * 示例 2：
 * <p>
 * 输入：digits = ""
 * 输出：[]
 * 示例 3：
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 * <p>
 * 来源：
 * https://blog.csdn.net/ajianyingxiaoqinghan/article/details/79682147
 *
 * @author hanxinghua
 * @create 2024/5/10
 * @since 1.0.0
 */
public class No17LetterCombinationsOfAPhoneNumber {

    public static void main(String[] args) {

        System.out.println(method1("23"));
        System.out.println(method1(""));
        System.out.println(method1("2"));

    }


    private static List<String> method1(String digits) {
        List<String> results = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return results;
        }

        Map<Character, List<String>> phoneNumberMap = new HashMap<>();
        phoneNumberMap.put('2', Arrays.asList(new String[]{"a", "b", "c"}));
        phoneNumberMap.put('3', Arrays.asList(new String[]{"d", "e", "f"}));
        phoneNumberMap.put('4', Arrays.asList(new String[]{"j", "k", "l"}));
        phoneNumberMap.put('6', Arrays.asList(new String[]{"m", "n", "o"}));
        phoneNumberMap.put('7', Arrays.asList(new String[]{"p", "q", "r", "s"}));
        phoneNumberMap.put('8', Arrays.asList(new String[]{"t", "u", "v"}));
        phoneNumberMap.put('9', Arrays.asList(new String[]{"w", "x", "y", "z"}));


        List<String> result = new ArrayList<>();
        backTrack(digits, 0, phoneNumberMap, result, results);

        return results;
    }

    private static void backTrack(String digits, int index, Map<Character, List<String>> phoneNumberMap, List<String> result, List<String> results) {

        // 结束条件 digits.length() == index ： index 从0开始，index最大值 比 digits.length()小1。
        // 所以当 digits.length() == index 时，是结束条件
        if (digits.length() == index) {
            results.add(String.join("", result));
            return;
        }

        List<String> strings = phoneNumberMap.get(digits.charAt(index));

        for (String string : strings) {
            result.add(string);
            // 递归处理下一个数
            backTrack(digits, index + 1, phoneNumberMap, result, results);
            // 恢复现场
            result.remove(result.size() - 1);
        }
    }


}
